package arithmetic2.day13;

import java.util.Arrays;

/**
 * 给定n为1-n的正整数，s为机器人的开始位置，e为目标位置，k为机器人必须走的步数，求出有多少种走法
 */
public class RobotDemo {
    public static void main(String[] args) {
        int count = f1(5, 4, 4, 2);
//        int[][] dp = new int[4 + 1][5 + 1];
//        for (int i = 0; i < dp.length; i++) {
//            Arrays.fill(dp[i], -1);
//        }
//        int count = f2(5, 4, 4, 2, dp);
        System.out.println(count);
        int count1 = f3(5, 4, 4, 2);
        System.out.println(count1);
    }

    /**
     * @param n
     * @param e:目标位置
     * @param rest:还有多少步需要走
     * @param cur:当前位置
     * @return
     */
    public static int f1(int n, int e, int rest, int cur) {
        if (rest == 0) {
            return cur == e ? 1 : 0;
        }
        //当机器人在1位置的时候只能往右走
        if (cur == 1) {
            return f1(n, e, rest - 1, cur + 1);
        }
        //当机器人在n位置的时候只能往左走
        if (cur == n) {
            return f1(n, e, rest - 1, cur - 1);
        }
        //当机器人在中间某个位置的时候可以往两边走
        return f1(n, e, rest - 1, cur - 1) + f1(n, e, rest - 1, cur + 1);
    }

    //加入一个dp的二维数来做缓存
    public static int f2(int n, int e, int rest, int cur, int dp[][]) {
        if (dp[rest][cur] != -1) {
            return dp[rest][cur];
        }
        if (rest == 0) {
            dp[rest][cur] = cur == e ? 1 : 0;
            return dp[rest][cur];
        }
        if (cur == 1) {
            dp[rest][cur] = f2(n, e, rest - 1, cur + 1, dp);
        } else if (cur == n) {
            dp[rest][cur] = f2(n, e, rest - 1, cur - 1, dp);
        } else {
            dp[rest][cur] = f2(n, e, rest - 1, cur + 1, dp) + f2(n, e, rest - 1, cur - 1, dp);
        }
        return dp[rest][cur];
    }

    //使用动态规划求解
    public static int f3(int n, int e, int rest, int cur) {
        int[][] dp = new int[rest + 1][n + 1];
        //初始化二维数组
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i == e ? 1 : 0;
        }
        //使用动态规划求解
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (j == 1) {
                    //这个值必须依赖右上方的值
                    dp[i][j] = dp[i - 1][j + 1];
                } else if (j == dp[0].length - 1) {
                    //这个值必须依赖左上方的值
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //处在中间位置的格子依赖左上方和右上方的值
                    dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1];
                }
            }
        }
        return dp[rest][cur];
    }
}
